public class Pilha implements Cloneable {
	NoPilha inicio;

	public Pilha() {
		inicio = null;
	}
	
	@Override
	protected Object clone() throws CloneNotSupportedException {
		return super.clone();
	}

	public void push(NoPilha no) {
		no.setNext(inicio);
		inicio = no;
	}

	public NoPilha pop() {
		if (inicio != null) {
			NoPilha aux = inicio;
			inicio = inicio.getNext();
			return aux;	
		}
		else return null;
	}

	public NoPilha top() {
		return inicio;		
	}

	public boolean isEmpty() {
		return inicio == null;
	}

	public Pilha ordenar() {
		if (this.isEmpty()) {
			return this;
		}
		
		Pilha aux1 = new Pilha();
		Pilha aux2 = new Pilha();
		boolean tag = false;
		do {
			while(!aux2.isEmpty()) {
				this.push(aux2.pop());
			}
			do {
				if (!tag) {
					tag = true;
					aux1.push(this.pop());
				}
				else if (this.top().getValor().compareTo(aux1.top().getValor()) > 0) {
					aux2.push(aux1.pop());
					aux1.push(this.pop());
				}
				else {
					aux2.push(this.pop());
				}
			} while(!this.isEmpty());
			tag = false;
		} while(!aux2.isEmpty());
		return aux1;
	}
}
